package com.kizuki.algorithm.leetcode;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 */
public class 在排序数组中查找元素的第一个和最后一个位置 {

    class Solution {
        public int[] searchRange(int[] nums, int target) {
            // 寻找>= target的index
            // 寻找>= target + 1的index
            int left = search(nums, target);
            int right = search(nums, target + 1);
            if (left == nums.length || nums[left] != target) {
                return new int[]{-1, -1};
            }
            return new int[]{left, right - 1};
        }

        private int search(int[] nums, int target) {
            int l = 0, r = nums.length;
            while(l < r) {
                int mid = (l + r) >> 1;
                if (nums[mid] >= target) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            return l;
        }
    }

}
